package com.practice;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author YJ
 * @data 2025/6/18 18:02
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class CompleteBinaryTree {
    /**
     * 给定一个二叉树，确定他是否是一个完全二叉树。
     *
     * 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，
     * 其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。
     * （第 h 层可能包含 [1~2h] 个节点）
     */
    /**
     * @param root TreeNode类
     * @return bool布尔型
     */
    public static boolean isCompleteTree(TreeNode root) {
        // write code here
        //空树一定是完全二叉树
        if (root == null)
            return true;
        //辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        //定义一个首次出现的标记位
        boolean notComplete = false;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            //标记第一次遇到空节点
            if (cur == null) {
                notComplete = true;
                continue;
            }
            //后续访问已经遇到空节点了，说明经过了叶子
            if (notComplete)
                return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }

    public static void main(String[] args) {
        //层序遍历：10 6 14 4 8 12 16
        TreeNode root = new TreeNode(10);
        TreeNode left1 = new TreeNode(6);
        TreeNode right1 = new TreeNode(14);
        TreeNode left1_left = new TreeNode(4);
        TreeNode left1_right = new TreeNode(8);
//        TreeNode right1_left = new TreeNode(12);
        TreeNode right1_right = new TreeNode(16);
        root.left = left1;
        root.right = right1;
        left1.left = left1_left;
        left1.right = left1_right;
//        right1.left = right1_left;
        right1.right = right1_right;
        boolean completeTree = isCompleteTree(root);
        if (completeTree) {
            System.out.println("是完全二叉树！");
        } else {
            System.out.println("不是完全二叉树!");
        }
    }
}
